/*
 * @lc app=leetcode.cn id=990 lang=typescript
 *
 * [990] 等式方程的可满足性
 */

// @lc code=start
class UnionFind {
  parent: number[];
  size: number[];
  count: number;
  constructor(n: number = 0) {
    this.parent = new Array(n).fill(0).map((_, i) => i);
    this.size = new Array(n).fill(1);
    this.count = n;
  }
  find(x: number): number {
    return this.parent[x] === x ? x : (this.parent[x] = this.find(this.parent[x]));
  }
  union(x: number, y: number): void {
    let rx = this.find(x);
    let ry = this.find(y);
    if (rx === ry) return;
    if (this.size[rx] > this.size[ry]) {
      [rx, ry] = [ry, rx];
    }
    this.parent[rx] = ry;
    this.size[ry] += this.size[rx];
    this.count--;
  }
  isConnected(x: number, y: number) {
    return this.find(x) === this.find(y);
  }
}
function equationsPossible(equations: string[]): boolean {
  const size = equations.length;
  const unionFind = new UnionFind(26);
  const base = 'a'.charCodeAt(0);
  // 将=操作加入并查集
  for (let i = 0; i < size; i++) {
    const equation = equations[i];
    let x = equation.charCodeAt(0) - base;
    let y = equation.charCodeAt(3) - base;
    if (equation[1] === '!') continue;
    unionFind.union(x, y);
  }
  // 判断!=操作的元素是否在并查集
  for (let i = 0; i < size; i++) {
    const equation = equations[i];
    let x = equation.charCodeAt(0) - base;
    let y = equation.charCodeAt(3) - base;
    if (equation[1] === '=') continue;
    if (unionFind.isConnected(x, y)) return false;
  }

  return true;
}
// @lc code=end
